/**
 * @file 字符串匹配
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-11
 * 
 * @copyright Copyright (c) 2021
 * 
 * 459.重复的子字符串
 */

#include <iostream>
#include <string>
#include <vector>
using namespace std;

template <class T>
void print(const T &t)
{
    typename T::const_iterator it = t.cbegin();
    for (; it != t.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

class Solution
{
public:
    bool repeatedSubstringPattern(string s)
    {
        // 若s可由某个子串重复n次，n最低取2吧；
        // 那么该子串必最少可以重复4次组成s+s；
        // 那s+s去掉头尾后必然可以由该子串重复构成2次，即s本身
        // 那问题就变成在s+s中找s
        // kmp
        int n = s.size();
        string text = s.substr(1, n - 1) + s.substr(0, n - 1);
        vector<int> next(n, 0);
        // cout << text << endl;
        // cout << s << endl;
        getNext(s, next);
        // testNext(s);
        int i = 0, j = 0;
        while (i < text.size() && j < n) {
            // 巨坑，这里j<s.size()会有问题，s.size是无符号整型
            // j==-1时与其比较会直接出循环 -1是无符号最大值嘛
            if (j == -1 || text[i] == s[j]) {
                ++i, ++j;
            } else {
                j = next[j]; // back j
            }
        }
        if (j == n) {
            return true;
        }
        return false;
    }

private:
    void getNext(string &t, vector<int> &next)
    {
        int j = -1;
        next[0] = -1;
        int i = 0;
        while (i < t.size()) {
            cout << "i = " << i << endl;
            cout << "j = " << j << endl;
            if (j == -1) {
                ++i, ++j;
            } else if (t[i] == t[j]) {
                ++i, ++j;
                next[i] = j;
            } else {
                j = next[j]; // back j
            }
        }
    }
    void testNext(string t)
    {
        cout << "模式串t = ";
        print(t);
        vector<int> next(t.size(), 0);
        getNext(t, next);
        cout << "Next数组 ";
        print(next);
    }
};

Solution solve = Solution();

void test459()
{
    string s = "abab";
    // string s = "aba";
    cout << solve.repeatedSubstringPattern(s) << endl;
}

int main()
{
    test459();
    return 0;
}